#include "ad_construct.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

void handle_root(const char* cword, int clen, int pernum, dfa * DFA, input_data & INPUT){
  char thword[MAX_WORD_LENGTH + 1];
  int i, blen = 2*clen;
  for (i=0; i<clen; i++){
    thword[i] = thword[i+clen] = cword[i];
  }
  thword[blen] = 0;
  if (blen > MAX_WORD_LENGTH){
    printf("Too small maximal length of forbidden word!\n");
    exit(1);
  }
  for (i=1; i<clen; i++){
    if (DFA->bad_suffix_trie(thword, clen + i, -1)) return;
  }
  if (DFA->bad_suffix_trie(thword + 1, 2 * clen - 1, -1)) return;
  DFA->add_word(thword);
  return;
}

i64 construct_antidictionary(grate_config & CONFIG, input_data & INPUT, words_queue * WORDS_QUEUE, dfa * DFA){
  i64 max_words_queue_size = 0;
  
  int i, clen = 3, pnum;
  i64 marker_pos;
  char cword[MAX_WORD_LENGTH], cper[MAX_WORD_LENGTH], ch;
  char nper[2][MAX_WORD_LENGTH];
  
  if (INPUT.ADD_X3){
    DFA->add_word("aaa");
    DFA->add_word("ababab");
  }
  else{
    WORDS_QUEUE->push_word("aaa", "ab");
  }
  
  WORDS_QUEUE->push_word("aab", "aa");
  WORDS_QUEUE->push_word("aba", "ab");
  WORDS_QUEUE->push_word("abb", "aa");

  WORDS_QUEUE->push_marker(marker_pos);
  
  while (! WORDS_QUEUE->is_empty()){
    if (WORDS_QUEUE->is_index(marker_pos)){
      if (clen < INPUT.ROOT_LENGTH){
        clen++;
        WORDS_QUEUE->push_marker(marker_pos);
        WORDS_QUEUE->pop_symbol();
        continue;
      }
      else break;
    }
    
    // there is a word in the queue starting at qbeg with (length = clen)
    for (i=0; i<clen; i++){
      cword[i] = WORDS_QUEUE->pop_symbol() + 'a';
    }
    cword[clen] = 0;

    pnum = 0;
    for (i=0; i<clen-1; i++){
      cper[i] = WORDS_QUEUE->pop_symbol() + 'a';
      pnum += (cper[i] == 'b');
      nper[0][i] = nper[1][i] = cper[i];
    }
    cper[clen-1] = 0;

    //if (pnum == 1){
    // This is wrong! There can be some untrivial cases
    if (pnum > 0){
      handle_root(cword, clen, pnum, DFA, INPUT);
    }

    if (clen < INPUT.ROOT_LENGTH){
      for (ch='a'; ch<='b'; ch++){
        cword[clen] = ch;
        cword[clen+1] = 0;
        if (DFA->bad_suffix_trie(cword, clen+1, -1)) continue;
        for (i=0; i<clen-1; i++){
          if (nper[ch-'a'][i] == 'b' && cword[clen%(i+1)] != ch){
            nper[ch-'a'][i] = 'a';
          }
        }
        if (ch == 'a') nper[0][clen-1] = 'b';
        else nper[1][clen-1] = 'a';
        nper[ch-'a'][clen] = 0;
        WORDS_QUEUE->push_word(cword, nper[ch-'a']);
      }
    }

    i64 cwqsz = WORDS_QUEUE->get_number_of_letters();
    if (cwqsz > max_words_queue_size){
      max_words_queue_size = cwqsz;
    }
  }
  delete WORDS_QUEUE;

  return max_words_queue_size;
}
